home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / gnu / smlltalk / smtk_11.zoo / Dictionary.st < prev    next >
Text File  |  1990-05-26  |  10KB  |  373 lines
  1. "======================================================================
  2. |
  3. |   Dictionary Method Definitions
  4. |
  5.  ======================================================================"
  6.  
  7.  
  8. "======================================================================
  9. |
  10. | Copyright (C) 1988, 1989, 1990 Free Software Foundation, Inc.
  11. | Written by Steve Byrne.
  12. |
  13. | This file is part of GNU Smalltalk.
  14. |
  15. | GNU Smalltalk is free software; you can redistribute it and/or modify it
  16. | under the terms of the GNU General Public License as published by the Free
  17. | Software Foundation; either version 1, or (at your option) any later version.
  18. | 
  19. | GNU Smalltalk is distributed in the hope that it will be useful, but WITHOUT
  20. | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  21. | FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  22. | details.
  23. | 
  24. | You should have received a copy of the GNU General Public License along with
  25. | GNU Smalltalk; see the file COPYING.  If not, write to the Free Software
  26. | Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  
  27. |
  28.  ======================================================================"
  29.  
  30.  
  31. "
  32. |     Change Log
  33. | ============================================================================
  34. | Author       Date       Change 
  35. | sbyrne      6 May 90      Fixed grow method to preserve associations in use in
  36. |              the dictionary instead of making new ones.  This
  37. |              should be faster, and doesn't break compiled methods
  38. |              that reference global variables when Smalltalk grows.
  39. |
  40. | sbyrne     24 Apr 90      Fix at:ifAbsent: to deal with failure better (and be
  41. |              a tad more efficient).  Kudos (or BarNone's,
  42. |              depending on preference) to Andy Valencia.
  43. |
  44. | sbyrne      7 Apr 90      Modified at:put: to resuse the existing Association
  45. |              if there is one, rather than create a new one all the
  46. |              time.  This was causing lossage when setting global
  47. |              variables in Smalltalk that previous usages weren't
  48. |              being changed.
  49. |
  50. | sbyrne     25 Apr 89      created.
  51. |
  52. "
  53.  
  54. Set variableSubclass: #Dictionary
  55.     instanceVariableNames: ''
  56.     classVariableNames: ''
  57.     poolDictionaries: ''
  58.     category: nil.
  59.  
  60. Dictionary comment: 
  61. 'I implement a dictionary, which is an object that is indexed by
  62. unique objects (typcially instances of Symbol), and associates another
  63. object with that index.  I use the equality operator = to determine
  64. equality of indices.' !
  65.  
  66. "### The initblocks variable should not be globally visible, I think"
  67. "This is a HACK HACK HACK.  We want to reference the InitBlocks global variable
  68. from within some methods in System Dictionary.  However, after this file
  69. redefines at:put: from the built-in one, and until UndefinedObject.st is 
  70. loaded, defining isNil for nil, at:put: for dictionaries does not work
  71. properly.  So we do it here.  The basic problem is that InitBlocks should
  72. maybe be kept elsewhere, and not be globally visible."
  73. Smalltalk at: #InitBlocks put: nil!
  74.  
  75. !Dictionary methodsFor: 'accessing'!
  76. add: anAssociation
  77.     | index |
  78.     index _ self findKeyIndex: anAssociation key.
  79.     (self basicAt: index) isNil
  80.     ifTrue: [ tally _ tally + 1].
  81.     self basicAt: index put: anAssociation.
  82.     ^anAssociation
  83. !
  84.  
  85. at: key put: value
  86.     | index assoc |
  87.     index _ self findKeyIndex: key.
  88.     (assoc _ self basicAt: index) isNil
  89.     ifTrue: [ self basicAt: index
  90.                put: (Association key: key value: value).
  91.           tally _ tally + 1 ]
  92.     ifFalse: [ assoc value: value ].
  93.     ^value
  94. !
  95.  
  96. at: key
  97.     ^self at: key ifAbsent: [ ^self error: 'key not found' ]
  98. !
  99.  
  100. at: key ifAbsent: aBlock
  101.     | assoc |
  102.     assoc _ self basicAt: (self findKeyIndex: key).
  103.     assoc isNil
  104.             ifTrue: [ ^aBlock value ]
  105.             ifFalse: [ ^assoc value ]
  106. !
  107.     
  108. associationAt: key
  109.     ^self associationAt: key ifAbsent: [ ^self error: 'key not found' ]
  110. !
  111.  
  112. associationAt: key ifAbsent: aBlock
  113.     | index assoc|
  114.     index _ self findKeyIndex: key.
  115.     assoc _ self basicAt: index.
  116.     assoc isNil ifTrue: [ ^aBlock value ]
  117.                 ifFalse: [ ^assoc ]
  118. !
  119.  
  120. keyAtValue: value ifAbsent: exceptionBlock
  121.     self associationsDo:
  122.         [ :assoc | value = assoc value
  123.                  ifTrue: [ ^assoc key ] ].
  124.     ^exceptionBlock value
  125. !
  126.  
  127. keyAtValue: value
  128.     ^self keyAtValue: value ifAbsent: []
  129. !
  130.  
  131. keys
  132.     | aSet |
  133.     aSet _ Set new: tally.
  134.     self keysDo: [ :aKey | aSet add: aKey ].
  135.     ^aSet
  136. !
  137.  
  138. values
  139.     | aBag |
  140.     aBag _ Bag new.
  141.     self do: [ :aValue | aBag add: aValue ].
  142.     ^aBag
  143. !!
  144.  
  145.  
  146.  
  147. !Dictionary methodsFor: 'dictionary testing'!
  148.  
  149. includesAssociation: anAssociation
  150.     | assoc |
  151.     assoc _ self associationAt: anAssociation key ifAbsent: [ ^false ].
  152.     ^assoc value = anAssociation value
  153. !
  154.  
  155. includesKey: key
  156.     self associationAt: key ifAbsent: [ ^false ].
  157.     ^true
  158. !
  159.  
  160. includes: anObject
  161.     self do: [ :element | element = anObject ifTrue: [ ^true ] ].
  162.     ^false
  163. !
  164.  
  165. occurrencesOf: aValue
  166.     | count |
  167.     count _ 0.
  168.     self do: [ :element | element = aValue
  169.                     ifTrue: [ count _ count + 1] ].
  170.     ^count
  171. !!
  172.  
  173.  
  174.  
  175. !Dictionary methodsFor: 'dictionary removing'!
  176.  
  177. removeAssociation: anAssociation
  178.     "### does this check the value as well as the key?"
  179.     self removeKey: anAssociation key ifAbsent: [].
  180.     ^anAssociation
  181. !
  182.  
  183. removeKey: key
  184.     ^self removeKey: key ifAbsent: [ ^self error: 'key not found' ]
  185. !
  186.  
  187. removeKey: key ifAbsent: aBlock
  188.     | index assoc |
  189.     index _ self findKeyIndexNoGrow: key ifAbsent: [ ^aBlock value ].
  190.     assoc _ self basicAt: index.
  191.     self basicAt: index put: nil.
  192.     tally _ tally - 1.
  193.     self rehashObjectsAfter: index.
  194.     ^assoc value
  195. !
  196.  
  197. remove: anObject
  198.     self error: 'remove: not allowed in Dictionary'
  199. !
  200.  
  201. remove: anObject ifAbsent: aBlock
  202.     self error: 'remove:ifAbsent: not allowed in Dictionary'
  203. !!
  204.  
  205.  
  206.  
  207. !Dictionary methodsFor: 'dictionary enumerating'!
  208. associationsDo: aBlock
  209.     super do: [ :assoc | aBlock value: assoc ]
  210. !
  211.  
  212. "These could be implemented more efficiently by doing the super do
  213.  directly, or doing the explicit scanning of the dictionary by hand"
  214. keysDo: aBlock
  215.     self associationsDo: [ :assoc | aBlock value: assoc key ]
  216. !
  217.  
  218. do: aBlock
  219.     self associationsDo: [ :assoc | aBlock value: assoc value ]
  220. !
  221.  
  222. collect: aBlock
  223.     | aBag |
  224.     aBag _ Bag new.
  225.     self do: [ :element | aBag add: (aBlock value: element) ].
  226.     ^aBag
  227. !
  228.  
  229. select: aBlock
  230.     | newDict |
  231.     newDict _ self species new.
  232.     self associationsDo:
  233.         [ :assoc | (aBlock value: assoc value)
  234.              ifTrue: [ newDict add: assoc ] ].
  235.     ^newDict
  236. !
  237.  
  238. reject: aBlock
  239.     self shouldNotImplement
  240. !
  241.  
  242. inject: value into: aBlock
  243.     self shouldNotImplement
  244. !!
  245.  
  246.  
  247.  
  248. !Dictionary methodsFor: 'misc math methods'!
  249.  
  250. = aDictionary
  251.     tally ~= aDictionary size ifTrue: [ ^false ].
  252.     self associationsDo:
  253.         [ :assoc | assoc value ~= (aDictionary at: assoc key
  254.                                            ifAbsent: [ ^false ])
  255.                      ifTrue: [ ^false ] ].
  256.     ^true
  257. !
  258.  
  259. hash
  260.     | hashValue |
  261.     hashValue _ tally.
  262.     self associationsDo:
  263.         [ :assoc | hashValue _ hashValue + assoc hash ].
  264.     ^hashValue
  265. !!
  266.  
  267.  
  268.  
  269. !Dictionary methodsFor: 'printing'!
  270.  
  271. printOn: aStream
  272.     aStream nextPutAll: self class name , ' (' .
  273.     self associationsDo:
  274.         [ :assoc | assoc key storeOn: aStream.
  275.                aStream nextPut: $,.
  276.            assoc value storeOn: aStream.
  277.            aStream nextPut: Character space ].
  278.     aStream nextPut: $)
  279. !!
  280.  
  281.  
  282.  
  283. !Dictionary methodsFor: 'storing'!
  284.  
  285. storeOn: aStream
  286.     | hasElements |
  287.     aStream nextPutAll: '(', self class name , ' new'.
  288.     hasElements _ false.
  289.     self associationsDo:
  290.         [ :assoc | aStream nextPutAll: ' at: '.
  291.                    assoc key storeOn: aStream.
  292.                aStream nextPutAll: ' put: '.
  293.            assoc value storeOn: aStream.
  294.            aStream nextPut: $;.
  295.            hasElements _ true ].
  296.     hasElements ifTrue: [ aStream nextPutAll: ' yourself' ].
  297.     aStream nextPut: $)
  298. !!
  299.  
  300.  
  301.  
  302. !Dictionary methodsFor: 'private methods'!
  303.  
  304. rehashObjectsAfter: index
  305.     "Rehashes all the objects in the collection after index to see if any of
  306.     them hash to index.  If so, that object is copied to index, and the
  307.     process repeats with that object's index, until a nil is encountered."
  308.     | i size count assoc |
  309.     i _ index.
  310.     size _ self basicSize.
  311.     c